/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/segment-tree-query-ii
   @Language: C++
   @Datetime: 16-02-09 08:30
   */

/**
 * Definition of SegmentTreeNode:
 * class SegmentTreeNode {
 * public:
 *     int start, end, count;
 *     SegmentTreeNode *left, *right;
 *     SegmentTreeNode(int start, int end, int count) {
 *         this->start = start;
 *         this->end = end;
 *         this->count = count;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
	/*
	 * @param root: The root of segment tree.
	 * @param start: start value.
	 * @param end: end value.
	 * @return: The count number in the interval [start, end]
	 */
	int query(SegmentTreeNode * root, int start, int end) {
		// write your code here
		if (root==NULL || root->count==0 || start>end) return 0;
		if(end>root->end) end=root->end;
		if(start<root->start) start=root->start;
		if(start==root->start && end==root->end) return root->count;
		int mid=(root->start+root->end)/2;
		if(start>mid) return query(root->right,start,end);
		if(end<=mid) return query(root->left,start,end);
		return query(root->left,start,mid)+query(root->right,mid+1,end);
	}
};
